package com.jxm.graph;

/**
 * @Author: jxm
 * @Description: 检测有向环的API设计
 * @Date: 2022/8/3 9:44
 * @Version: 1.0
 */
public class DirectedCycle {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录图中是否有环
    private boolean hasCycle;
    //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;

    public DirectedCycle(Digraph G){
        this.marked = new boolean[G.V()];
        this.hasCycle = false;
        this.onStack = new boolean[G.V()];
        //找到图中每一个顶点，让每一个顶点作为人口，调用一次dfs进行搜系
        for (int v = 0; v < G.V(); v++) {
            //判断如果当前顶点还没有搜索过，则调用dfs进行搜索
            if(!marked[v]){
                dfs(G,v);
            }
        }
    }

    /**
     * 基于深度优先搜索，检测图G中是否有环
     * @param G
     * @param v
     */
    private void dfs(Digraph G,int v){
        //把顶点v标记为已经搜索
        marked[v] = true;
        //把当前顶点进栈
        onStack[v] = true;
        //进行深度搜索
        for (Integer w : G.adj(v)) {
            //判断如果当前顶点w没有被搜索过，则继续递归调用dfs
            if(!marked[w]){
                dfs(G,w);
            }
            //判断当前顶点是否在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索状态，那么现在又要搜索一次，证明检测到环
            if(onStack[w]){
                hasCycle = true;
                return;
            }

        }
        //把当前顶点出栈
        onStack[v] = false;

    }

    /**
     * 判断图中是否有环
     * @return
     */
    public boolean hasCycle(){
        return hasCycle;
    }
}
